import java.util.Arrays;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 22652
 * Date: 2024-03-25
 * Time: 23:49
 */
public class test_3 {
    public static int jewelleryValue(int[][] frame) {
        // 1. 创建 dp 表
        int n = frame.length + 1;
        int m = frame[0].length + 1;
        int[][] dp = new int[n][m];
        // 2. 初始化
        // 3. 填表
        for (int i = 1; i < n; i++) {
            for (int j = 1; j < m; j++) {
                dp[i][j] = Math.max(dp[i][j - 1] + frame[i - 1][j - 1], dp[i - 1][j] + frame[i - 1][j - 1]);
            }

        }
        for (int i = 0; i < n; i++) {
            System.out.println(Arrays.toString(dp[i]));
        }
        // 4. 返回值
        return dp[n - 1][m - 1];

    }

    public static void main(String[] args) {
        int[][] st = {{1, 3, 1}, {1, 5, 1}, {4, 2, 1}};
        System.out.println(jewelleryValue(st));

    }
}
